(a) Field of the Invention
The present invention relates to a decoding apparatus for LDPC (Low-Density Parity-Check) codes using sequential decoding, and a method thereof. More specifically, the present invention relates to a decoding apparatus for LDPC codes and a method thereof that decode LDPC codes when receiving data encoded with LDPC codes on a channel having consecutive output values.
(b) Description of the Related Art
LDPC codes are linear block codes invented by Gallager in 1962, and are defined as a sparse parity-check matrix in which most of the elements are zero.
The LDPC code was almost forgotten since the expense of its implementation was too high at that time. It was recently rediscovered, in 1995, and was improved as an irregular LDPC code by generalization in 1998.
A probabilistic decoding algorithm for the LDPC codes was also invented at the time of Gallager's first discovery of the LDPC codes. The performance of the LDPC codes decoded by the algorithm is remarkably high, and was more improved by expansion of a codeword from binary codes to nonbinary codes.
Like turbo codes, the LDPC codes have a bit error rate (BER) close to the Shannon channel capacity limit. Irregular LDPC codes known to have a highest performance only need 0.13 more dB from the Shannon channel capacity to get a bit error rate (BER) of 10−6 when its code length is about one million (106) bits in the additive white Gaussian noise (AWGN) channel environment. For that reason, the irregular LDPC codes are suitable for applications that require a high-quality transmission environment having an extremely low bit error rate (BER).
Message-passing decoding algorithms are used for decoding the LDPC codes. The most representative message-passing decoding algorithm is the sum-product algorithm. The sum-product algorithm uses summations and multiplications as basic operations of decoders, and its performance is determined by the construction method of check nodes and variable nodes of the LDPC codes.
Korean Patent Application No. 2001-50423 (filed on Aug. 21, 2001) by the applicant of the present invention discloses an invention under the title of “Apparatus for Adaptively Determining Maximum Number of Decoding Iterations for LDPC Decoder Using Signal-to-Noise Ratio Estimation, Method thereof, LDPC Decoding Apparatus Including the Apparatus, and Method thereof”.
More specifically, the apparatus for adaptively determining the maximum number of decoding iterations for an LDPC decoder according to the cited invention estimates a signal-to-noise ratio corresponding to a received LDPC encoded signal, and adaptively determines the maximum number of decoding iterations corresponding to the estimated signal-to-noise ratio based on a memory storing maximum numbers of decoding iterations corresponding to various signal-to-noise ratios.
According to the cited invention, the signal-to-noise ratio corresponding to the received signal is estimated to adaptively determine the maximum number of decoding iterations that satisfies a required performance. This reduces the average number of decoding iterations and hence a delay of the signal, but disadvantageously increases the number of calculations.
Korean Patent Application No. 2002-34987 (filed on Jun. 21, 2002) describes an invention under the title of “Decoding Method of Error Correction Codes Using Approximation Function”.
More specifically, the decoding method of error correction codes using an approximation function according to the cited invention is directed to a method for decoding error correction codes using an approximation function so as to simplify the decoding operation when using the approximation function for a decoding process of error correction codes in a digital data receiver. The decoding method includes: selecting a function containing no negative values and that is symmetrical about a function axis; dividing a variable interval into at least three intervals, and selecting a linear function approximating the function by the respective intervals; performing an operation on two input message values to determine the variable interval for the two values; operating the linear function corresponding to the interval to determine two function values; and determining the difference between the two function values. The cited invention simplifies the decoding function to reduce the number of calculations and is also applicable to other types of codes. The method is, however, simply reducing the number of calculations by simplification of the calculations using a function for reducing the number of decoding operations.
Korean Patent Application No. 2003-44955 (filed on Jul. 3, 2003) discloses an invention under the title of “Method and System for Decoding LDPC Codes”.
More specifically, the cited invention provides a method for transmitting a message using LDPC codes. According to the cited invention, an input message is encoded to generate LDPC codes according to a parity-check matrix constructed to restrain a sub-matrix of the parity-check matrix. Here, the LDPC codes are transmitted on a wireless communication system (e.g., a satellite network), and a receiver on the wireless communication system iteratively decodes the received LDPC codes according to a signal constellation related to the LDPC codes. The receiver decodes the LDPC codes at least twice, and then iteratively regenerates a signal array bit matrix. The cited invention generates codes restraining a sub-matrix of the parity-check matrix of LDPC codes to facilitate encoding of the codes and uses a signal constellation for decoding the codes.
However, the decoding apparatus using the conventional message-passing decoding algorithm also generates update information for the respective variable nodes and collectively reflects the update information in the calculations to update a message for each node, so there is a demand for a larger size of memory that is necessary for message storage of a message-passing decoder and the convergence rate of the message-passing decoder is retarded.